#include<iostream>
using namespace std;
 struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 };
class Solution {
public:
    TreeNode* insertIntoBST(TreeNode* root, int val) {
        if(root==NULL)return new TreeNode(val);
        if(root->val<val)root->right=insertIntoBST(root->right,val);
        if(root->val>val)root->left=insertIntoBST(root->left,val);
        return root;
    }
};